﻿
namespace SortAndDatastruct {
    /// <summary>
    /// 插入排序算法[不需要额外空间]
    /// 算法效率O(N*N)
    /// 对少量数排序有效
    /// </summary>
    class InsertionSort : ISort {
        /// <summary>
        /// 排序接口
        /// </summary>
        /// <param name="Array">待排序的数组</param>
        internal override void Sort(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            for (int i = 1; i < Array.Length; ++i) {
                int key = Array[i];
                int j = i - 1;
                while (j >= 0 && key < Array[j]) {
                    Array[j + 1] = Array[j--];
                }
                Array[j + 1] = key;
            }
        }
    }
}
